/**
 * 给定二进制数与X，第X、2X、3X、...的1的数量为该数的价值
 * [1, N]的价值和称为N的累加价值
 * 给定K与X，求累加价值不超过K的最大整数 
 * 
 * 显然二分，用数位DP求满足条件1的数量
 */
using llt = long long;

vector<int> G;
// Dijk, i表示当前数位，j表示cnt，k表示X
int X;
llt D[70][70][70];

llt dfs(int pos, int cnt, bool lead, bool limit){
    if(-1 == pos) {
        return cnt; 
    }
    if(not lead and not limit and -1 != D[pos][cnt][X]) {
        return D[pos][cnt][X];
    }
    int last = limit ? G[pos] : 1; 
    
    llt ans = 0;
    for(int i=0;i<=last;++i){
        if(1 == i && (pos + 1) % X == 0){
            ans += dfs(pos - 1, cnt + 1, false, limit&&last==i);
        }else{
            ans += dfs(pos - 1, cnt, lead&&0==i, limit&&last==i); 
        }        
    }

    if(not lead and not limit){
        D[pos][cnt][X] = ans;
    }    
    return ans;
}

llt digitDP(llt n){
    G.clear();
    while(n){
        G.emplace_back(n & 1);
        n >>= 1;
    }
    auto tmp = dfs(G.size() - 1, 0, true, true);
    return tmp;
}

class Solution {
public:
    long long findMaximumNumber(long long k, int x) {
        static bool b = true;
        if(b){ // 所有样例只初始化一次
            memset(D, -1, sizeof(D));
            b = false;
        }

        X = x;
        llt left = 1, right = 1E17, mid;
        do{
            mid = (left + right) >> 1;
            auto tmp = digitDP(mid);
            if(tmp <= k) left = mid + 1;
            else right = mid - 1;
        }while(left <= right);
        return right;
    }
};